package com.acyouzi.leetcode.unionfind;

/**
 * 17/9/17 21:53
 *
 * @author sunxu
 */
public class FriendCircles {
  public int[] group;
  int count;
  public int findCircleNum(int[][] M) {
    group = new int[M.length];
    count = M.length;
    for (int i = 0; i < group.length; i++) group[i] = i;
    for (int i = 0; i < M.length; i++) {
      for (int j = i+1; j < M.length; j++) {
        if (M[i][j] == 1){
          addGroup(i,j);
        }
      }
    }
    return count;
  }
  public int findRoot(int a){
    while (group[a] != a){
      a = group[a];
    }
    return a;
  }
  public void addGroup(int a, int b){
    int aroot = findRoot(a);
    int broot = findRoot(b);
    if (aroot == broot) return;
    group[broot] = aroot;
    count--;
  }
}
